package com.javabasic.algorithm.leetcode;

import java.util.TreeSet;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/7/8 21:36
 * @Version 1.0
 **/
public class DivingBoardLCCI {

    /**
     * 暴力解法，遍历每一种可能性 时间复杂度：O(2*N)
     * @param shorter
     * @param longer
     * @param k
     * @return
     */
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k==0) {
            return new int[0];
        }
        TreeSet<Integer> result = new TreeSet<>();
        for (int i = 0; i <= k; i++) {
            result.add(shorter * i + longer * k - i);
        }
        int[] ints = new int[result.size()];
        AtomicInteger tag = new AtomicInteger(0);
        result.stream().forEach(ele -> {
            ints[tag.get()] = ele;
            tag.getAndIncrement();
        });

        return ints;
    }

    /**优化
     * 解法二：优化逻辑思维
     * 理解：
     * 总共有k块木板
     * 1. 当shorter==longer  只会有一种情况
     * 2. 当shorter!=longer  我们可以从shorter或longer长度的木板中的一个来看，他们可能被使用的情况有0、1、2、、、n 总共(n+1)种情况
     * 而且这n种情况下获得到值也不一样，因为每种情况shorter和longer的个数都不一样[当shorter!=longer时，shorter和longer的个数不一样那么最终的值也会不一样]
     * @param shorter
     * @param longer
     * @param k
     * @return
     */
    public int[] divingBoard2(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        int len;
        if (shorter == longer) {
            len = 1;
        } else {
            len = k + 1;
        }
        int[] result = new int[len];
        for (int i = 0; i < len; i++) {
            result[i] = shorter * (k - i) + longer * i;
        }
        return result;
    }
}
